package com.kevinkk.tree;

/**
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 *
 * 满二叉树的节点个数是 2 ^ {深度} - 1
 * 而完全二叉树可以看作若干个满二叉树和一个（或者0个）单独节点构成
 */

public class CountCompleteTreeNodes {
    class Solution {
        public int countNodes(TreeNode root) {
            if(root == null) return 0;
            TreeNode left = root.left, right = root.right;
            int leftDepth = 0, rightDepth = 0;
            while(left != null){
                left = left.left;
                leftDepth ++;
            }
            while(right != null){
                right = right.right;
                rightDepth ++;
            }

            if(leftDepth == rightDepth) return (2 << leftDepth) - 1;
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
}
